package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

import java.util.Stack;

/**
 * 剑指offer-面试7
 * 用两个栈实现队列
 * 用两个栈实现一个队列。队列的生命如下，请事先它的两个函数appendTail和deleteHead，分别完成在
 * 队列尾部插入节点和在队列头部删除节点的功能。
 */
public class Mianshi7 {
    public static class QueueWithStack<T> {
        private Stack<T> stack1;
        private Stack<T> stack2;

        public QueueWithStack() {
            this.stack1 = new Stack<>();
            this.stack2 = new Stack<>();
        }

        public void appendTail(T value) {
            if (this.stack1 == null) {
                this.stack1 = new Stack<>();
            }
            if (this.stack2 == null) {
                this.stack2 = new Stack<>();
            }
            if (this.stack1.isEmpty()) {
                while (!this.stack1.isEmpty()) {
                    this.stack1.push(this.stack2.pop());
                }
            }
            this.stack1.push(value);
        }

        public T deleteHead() throws Exception {
            if (this.stack1 == null) {
                this.stack1 = new Stack<>();
            }
            if (this.stack2 == null) {
                this.stack2 = new Stack<>();
            }
            if (this.stack2.isEmpty()) {
                while (!this.stack1.isEmpty()) {
                    this.stack2.push(this.stack1.pop());
                }
            }
            if (!this.stack2.isEmpty()) {
                return this.stack2.pop();
            } else {
                throw new Exception("栈为空");
            }

        }

        public void appendTail1(T value) {
            this.stack1.push(value);
        }

        public T deleteHead1() throws Exception {
            if (this.stack2.isEmpty()) {
                while (!this.stack1.isEmpty()) {
                    this.stack2.push(this.stack1.pop());
                }
            }
            if (!this.stack2.isEmpty()) {
                return this.stack2.pop();
            } else {
                throw new Exception("栈为空");
            }
        }
    }

    public static void main(String[] args) throws Exception {
        QueueWithStack<Integer> queue = new Mianshi7.QueueWithStack<>();
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        System.out.println(queue.deleteHead());
        queue.appendTail(4);
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        queue.appendTail1(1);
        queue.appendTail1(2);
        queue.appendTail1(3);
        System.out.println(queue.deleteHead());
        queue.appendTail1(4);
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
    }


}
